Programs can be executed by processing with multiple threads (multi-threading) in order to utilize a shared memory type multi-processor system effectively. In the multi-threading, threads can be executed in parallel by sharing the virtual space of the process. In switching the threads, there is no need to switch the virtual space, and only the minimum context switching is required. For this reason, it is possible to improve the performance of the parallel processing by the multi-processor system. These threads may be accessing shared data from data containers.
Data containers are a common abstractions in Object Oriented languages such as Java™. An instance of a data container holds a collection of other objects usually of the same data type. For example, DataContainer can include a container structure where data entries resides. Data containers are also thread safe. In other words, contents of a data container can be mutated by multiple threads concurrently. Yet contents of a data container do not get corrupted. In order to become thread safe, data containers implement some type of container locking, be it on the global container level itself, or on more fine grained level of container elements themselves.
However, overall system performance can seriously degrade when the locking mechanism is not appropriately implemented. Having a lock protected data container which is locked on every access can cause unacceptable levels of contention (this occurs whenever one process or thread attempts to acquire a lock held by another process or thread) especially in cases where batching operations on data container do not cause the state of container to become invalid or corrupted.
Every put, remove, get and other invoked data entries operations eventually end up in the data container. Therefore, the data container should be implemented in a way that does not impede overall system throughput. It is also known that the data container's memory footprint can not grow indefinitely because it would eventually run out of memory. To resolve the limited memory footprint, certain data entries are periodically evicted from the data container according to an eviction algorithm.
LRU (Least Recently Used) eviction algorithm, although simple and easy to understand, under performs in cases of weak access locality (e.g. one time access entries are not timely replaced, entries to be accessed soonest are unfortunately replaced). Recently, a new eviction algorithm—LIRS (Low Inter-Reference Recency Set Replacement) has gathered a lot of attention because it addresses weak access locality shortcomings of LRU yet it retains LRU's simplicity.
However, no matter which eviction algorithm is used, if eviction is not implemented in a scalable low lock contention approach, it can seriously degrade overall system performance. In order to perform any meaningful selection of entries for eviction, the data container has to be locked until appropriate eviction entries are selected. Having such a lock protected data container in turn causes high lock contention offsetting any eviction precision gained by sophisticated eviction algorithms.